package demo.hw;

import java.util.Arrays;

public class _最大花费金额 {
    public static void main(String[] args) {
        /*
         * 一、题目描述
         * 双十一众多商品进行打折销售，小明想购买自己心仪的一些物品，但由于受购买资金限制，所以他决定从众多心仪商品中购买三件，而目想尽可能的花完资金。
         * 现在请你设计一个程序帮助小明计算尽可能花费的最大资金数额。
         * 二、输入描述
         * 输入第一行为一维整型数组M,数组长度小于100，数组元素记录单个商品的价格，单个商品价格小于1000;
         * 输入第二行为购买资金的额度R,R小于100000；
         * 输入格式是正确的，无需考虑格式错误的情况。
         * 三、输出描述
         * 输出为满足上述条件的最大花费额度；
         * 如果不存在满足上述条件的商品，请返回-1.
         * 四、测试用例
         * 测试用例1
         * 输入
         * 10 20 30 40 50
         * 100
         * 输出
         * 100
         * 说明
         * 例如组合(50,40,10)或(50,30,20)都正好等于预算100，故最大花费为100。
         * 测试用例2
         * 输入
         * 5 8 12 6 15
         * 20
         * 输出
         * 19
         *
         * 输入
         * 23 26 36 27
         * 78
         * 输出
         * 76
         * 说明
         * 23+26+27=76,最接近且小于78
         *
         * 输入
         * 23 30 40
         * 26
         * 输出
         * -1
         * 说明
         * 无法组合出满足三件之和小于26，故输出-1
         */
        int[] nums = { 23, 26, 36, 27};
        int k = 78;
        int max = -1;
        // 思路：
        // 求三数之和==k || 三数之和接近k的最大值 sum<k条件下 max=sum
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++) {
            int left = i+1, right = nums.length - 1;
            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                if (sum == k) {
                    System.out.print(nums[i]+","+nums[left]+","+nums[right]);
                    max=sum;
                    System.out.println();
                    break;
                } else if (sum <k) {
                    System.out.print(nums[i]+","+nums[left]+","+nums[right]);
                    System.out.println();
                    max=sum;
                    left++;
                } else {
                    right--;
                }
            }
        }

        System.out.println(max);
    }
}
